The invention relates to techniques for automated paragraph layout.
Paragraph layout in a document production application involves selection and placement of line breaks to produce a visually pleasing appearance within a paragraph cell that defines the space allotted for the paragraph. Changes in the style of the text, e.g., fonts, formats, line heights, and point size, can complicate the task, particularly when layout is performed within non-rectangular shapes. In addition, text styles and shape complexity can significantly increase computational overhead and processing time.
A number of techniques exist for automated paragraph layout. Many implement a line-by-line approach. Line-by-line techniques generally start with a first line, assign penalty values for possible breaks in that line, and choose the best possible line break for that line. After the first line is defined, a second line is analyzed and defined in a similar manner. Line-by-line techniques continue through a paragraph, defining each line and moving on to the next. Although these techniques minimize penalty values for each line, they may not optimize paragraph layout because the cumulative result of each collection of line breaks is never considered.
One type of more sophisticated technique for automated paragraph layout involves the formulation of a tree structure representing all possible lines for a given paragraph. This type of technique assigns a penalty value to each possible line, and picks a path through the tree with the lowest cumulative penalty. Although this is generally effective, it is very time and memory-intensive. Extensive use of system resources and protracted processing time is generally undesirable in document production, especially in light of the increasing complexities of document content.
Still other techniques make use of dynamic programming and failure functions to create algorithms that run in linear time with one backward pass through the text. See D. S. Hirschberg and L. L. Lamore, “New Applications of Failure Functions,” Journal of the Association for Computing Machinery, vol. 34, no. 3, July 1987. These dynamic programming techniques are generally less memory-intensive and very quick compared to the tree structure techniques. Complex shapes can undermine the effectiveness of such techniques, however, limiting their general application to paragraph layout. In particular, the Hirschberg/Lamore approach has proved inapplicable for shapes that deviate from a constant line width.